Field of the Embodiments
The embodiments are directed to cellular carrier resource scheduling and pricing and its relation to carrier aggregation. More particularly, a novel algorithm is applied to account for varying user utility functions and revised cellular standards reflecting carrier aggregation capabilities.
Description of Related Art
As smart phones and mobile computing become more commonplace, the demand on cellular networks is on the rise. Given the limited frequency band available to cellular providers, this demand can exceed network capacity. Looking at the demand from the perspective of the user, smart phones have a large number of applications and most of them require network resources. In the current 3GPP 4G LTE standard, users are limited to one carrier. In instances where one carrier does not provide enough bandwidth for a given user, this user would experience a diminished Quality of Serve (QoS) with slower applications. A new feature of the 3GPP LTE-Advanced cellular standard that will work to solve these problems, from the perspective of the network and user, is carrier aggregation.
This new feature of 4G LTE-Advanced allows for multiple carriers to be used by a single user. The additional carriers per user will allow users to use their smart phones without a loss of QoS. Carrier aggregation also helps to lessen the load on the network. If a carrier outside the traditional cellular frequency band can be used, the stress on the traditional cellular band will diminish. Frequency bands that may allow for this type of on-demand carrier aggregation can be in the public service band, previously reserved military bands, or other non-traditional cellular bands.
The addition of carrier aggregation allows for higher data rates for users in addition to a lower demand on current cellular bands if non-traditional, on-demand bands are used for secondary carriers, but some outstanding technical implementation considerations remain. The issue of resource allocation and the determination of shadow prices across multiple carriers must be considered. The term shadow price can be defined as the network resource price resulting from a demand on the network in the form of user bids. This means the price of network resources, or Physical Resource Blocks (PRB), will be more expensive in the case where users demand more resources and less expensive in the case of less demand.
In addition to the complication of carrier aggregation when considering how to allocate resources and determine shadow prices, smart phones run various applications all with differing utility functions. The overall device utility function is the sum of the individual application utility functions. Since the device utility function will be a combination of inelastic and elastic application utility functions, it will have both inelastic and elastic regions. Traditional resource allocation algorithms used for cellular networks, like the Frank Kelly algorithm, assume that the user utility functions will be strictly elastic, or concave, functions (see F. P. Kelly, A. K. Maulloo, and D. K. H. Tan., “Rate control for communication networks: shadow prices, proportional fairness and stability,” Journal of the Operational Research society, 49(3):237-252, 1998, which is incorporated herein by reference). This assumption allows for one unique optimal solution for each user's resource allocation. A more realistic resource allocation approach would be to consider a utility function that is representative of a prioritized sum of application utility functions. This type of utility function requires changes to the traditional methods of resource allocation, namely the Frank Kelly algorithm.
Previous work done for resource allocation is discussed herein. It is important to consider utility functions, costs to the users. and possible aggregation scenarios. In addition, previous work on resource allocation algorithms, including the Frank Kelly algorithm, provides a basis for the algorithms proposed herein.
When assigning resources to specific users, the network attempts to optimize the utility and cost across the network. Utility functions are unique to each user and depend on how the user is using the network resources. Traditionally, utility functions for cellular networks are assumed to be strictly concave. That is, there is diminishing return as a user is allocated more and more resources. This assumption allows for algorithms like the Frank Kelly algorithm to find unique resource allocation solutions through either iterative or algebraic solutions.
More generically, there are a few classes of utility functions that can be associated with different types of applications. The three types of utility functions are strictly inelastic utility functions, strictly elastic utility functions and a combination of the two functions where a minimum rate is required, but after that minimum rate, the utility function resembles the elastic utility functions. An illustration of these types of utility functions is seen in FIG. 1.
When considering smart phones comprised of many applications, one can group these applications into the three simple groups of utility functions considered in the previous paragraph. Applications like telephone calls can be placed in the strictly inelastic category. Each phone uses a particular codec that has a minimum data requirement to translate the voice over the network. No additional resources are used beyond this data rate because the amount of data required to send voice information over the network is static. This gives it the step function shape seen in FIG. 1(a).
Applications like email, social networking, and other applications that are not time critical can be placed in the strictly elastic utility function category. An email may be megabytes of data, but how long it takes to get to the user is not as critical. Obviously, a higher data rate gives the user a better QoS, but since the user is not notified until the email is in queue there is effectively no minimum data rate requirement. Therefore, any amount of resources from the network that can be dedicated to these resources is useful to these types of applications. An example of this “diminishing returns” model is seen in FIG. 1(b).
The last category of applications on a smart phone involves applications that resemble a combination of the inelastic and elastic utility functions. These applications consist of video streaming applications, such as YOUTUBE or time sensitive applications like SKYPE (including video calls). Video streaming specifically requires a minimum data rate for coarse resolution, so that the user can see what is on the screen. However, unlike voice calls, added data rate can increase the resolution of the video with diminishing return like the strictly elastic applications. This is because once the user is able to see what is on the screen, additional resolution only provides the video with greater detail. For example, instead of receiving a low quality video, the user may be able to make out details of the background in the streaming movie. This type of application may have a utility function like the one seen in FIG. 1(c).
Based on smart phones available today, a user can have multiple applications, each with different utility functions, running simultaneously on a single device. This complicates the traditional notion of a strictly concave utility function for cellular phone users. Later herein, consideration is taken on how to construct a user utility function from a combination of application utility functions prioritized based on what applications are most important to any given user. An example table of possible data rate requirements for certain applications is provided in Table 1.
TABLE 1Data Rate Requirements for Common ApplicationsMinimumMaximumApplicationData RateData RateVoice Calls16 kbps64 kbpsEmailsN/AN/AVideo2/6 Mbps4/8 Mbps(SD/HD)
Another important consideration when determining how to allocate resources is the cost functions for each user. There are some previously explored methods that select wireless networks solely based on cost to the user. The cost, in combination with the utility function for each user, is used to determine optimal resource allocation through algorithms like the Frank Kelly algorithm, discussed below. These cost functions must consider many factors. The first consideration is the price of the network resources themselves.
Each cellular provider or network sets a price for each resource block allocated to the user. This price structure can take many forms, but in most cases is assumed to be linear. That is, each resource block costs a constant dollar amount to the user. This is typically the only cost considered in the most simplistic solutions for resource block allocations across a network.
Another important element of the cost to the user is in the form of energy costs. Mobile devices work on battery power and require different amounts of power given the frequency band in which they are operating, whether they are on the fringes of the network or the main coverage area, etc. This means there is an additional energy cost for the amount of rate that is allocated to a user or the amount of time the user will be transmitting.
Other costs may include latency based on channel propagation properties and processing time. The evaluation of this cost is complex, since channel properties, frequency band of operation, user hardware, and base station hardware greatly change the cost of latency. This element of cost is considered negligent in the embodiments herein, but one skilled in the art recognizes that such may be incorporated to attain a more comprehensive model. The relevant costs and utility functions will be considered when allocating rate to the users based on maximizing the utility for each user and therefore across the network.
There are several different fairness models for rate allocation across a network as well as different algorithms for determining these rates. Two examples of fairness models include proportional fairness, and maxmin fairness. In addition to these fairness models, an optimal solution needs to be determined. These optimal solutions are typically referred to as Pareto optimal solutions. When considering how to determine Pareto optimal solutions, it is important to consider Pareto inefficient, Pareto efficient, and infeasible solutions. For the case of distributing solutions, infeasible solutions are those that require more resources than are available on the network. Pareto inefficient solutions are those solutions that do not allocate all network resources. Finally, Pareto optimal, or Pareto efficient, solutions are those solutions that distribute all of the network resources, which is also referred to as the Pareto front. Based on monotonically increasing utility functions, Pareto optimal solutions guarantee a maximization of the network utility. FIG. 2 represents the entire solution space including the Pareto inefficient solutions, Pareto optimal solutions, and infeasible solutions. For the present embodiments, it is considered that a network will want to distribute all of its resources in order to maximize the overall network utility.
Not all fairness models achieve Pareto optimal solutions, but can be used in conjunction with Pareto optimality to determine an overall fair and optimal solution of resource allocation. The first fairness model that is considered is maxmin fairness. This fairness models seeks to achieve the highest utility for users that have the lowest limits of utility. For example, this means that a user restricted to low channel capacity based on user equipment would have the utility function maximized. Equation (1) expresses the maxmin fairness model, where Ui(ri) is the utility function of a user i and ri is the rate allocated to that user. The use of maxmin fairness is rarely considered in the case of wireless networks and has limited use in the case of bottlenecks and other rate limitations. This fairness model is not used with the present embodiments, but is noted for its possible uses for maximizing current Release 8/9 capable devices in the presence of a growing number of Release 10 capable devices in the future.
                              r          i                =                  arg          ⁢                                          ⁢                                    max                              r                i                                      ⁢                                          min                i                            ⁢                                                U                  i                                ⁡                                  (                                      r                    i                                    )                                                                                        (        1        )            The second fairness model is proportional fairness. In this model, some rate must be allocated to every user. This is done through setting the condition of fairness to be a proportion, like the name suggests. This makes it impossible to set a users allocation to zero without setting the efficiency of the network to zero. Equation (2) represents the proportional fairness model, where Ui(ri) is the utility function of a user i and ri is the rate allocated to that user. Because this resource does not disenfranchise any given user, it will be considered as the appropriate fairness model for the present embodiments. This fairness model is the fairness basis for the Frank Kelly algorithm, which is modified in the present embodiments to allow for carrier aggregation.
                              r          i                =                  arg          ⁢                                          ⁢                                    max                              r                i                                      ⁢                                          ∏                                  i                  =                  1                                n                            ⁢                                                          ⁢                                                U                  i                                ⁡                                  (                                      r                    i                                    )                                                                                        (        2        )            There are a few algorithms that can be used to achieve rate allocation with each fairness model. Two examples of these algorithms include the water-filling algorithm and the Frank Kelly algorithm. The water-filling algorithm can be simply explained as a method for equally distributing the resources and filling users to capacity. This algorithm does not necessarily maximize the utility across the network, since more utility may be gained by allocating more resources to a user with higher capacity. This algorithm uses the maxmin fairness model, since it works to maximize the utility for the user with a limit to the resources it is capable of using.
The second algorithm, which uses proportional fairness, is the Frank Kelly algorithm. This algorithm is an iterative process for determining rate allocation as well as the price the network should charge for given sets of resources. The iterative nature of the solution allows users to bid on resources until the allocated rate matches its optimally determined rate based on utility functions and cost.
In some instances, the price the network should charge for its resources is unknown as well. Since it is important for the user to maximize its utility less the cost of the network resources, knowledge of the shadow price is required. This is especially true in the case of carrier aggregation where demand of secondary carriers is a largely unknown. On-demand and opportunistic secondary carriers have never before been exercised as cellular carriers. Accordingly, there is a need in the art for a process to determine optimal rate allocation as well as network shadow price in view of the evolving primary and secondary carrier scenarios, i.e., carrier aggregation scenarios, and increasing cellular user demands.